/**
 * 插入排序
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  console.time("插入排序耗时");
  for (let i = 1; i < nums.length; i++) {
    // 已排序区间 [0, i) ，未排序区间 [i , len)
    // 将 nums[i] 插入到区间 [0, i) 使之成为有序数组

    // 先暂存这个元素，然后之前元素逐个后移，留出空位
    let temp = nums[i];
    // let j = i;
    // // 从右往左遍历有序序列
    // while (j > 0 && temp < nums[j - 1]) {
    //   // 只要nums[j]比前一个元素nums[j-1]小，将nums[j-1]移动到nums[j]
    //   nums[j] = nums[j - 1];
    //   j--;
    // }

    let j;
    for (j = i; j > 0 && temp < nums[j - 1]; j--) {
      nums[j] = nums[j - 1];
    }

    // 找到位置j，将i的值放在j上
    nums[j] = temp;
  }
  console.timeEnd("插入排序耗时");
  return nums;
};

let arr = sortArray([6, 9, 0, 4, 8, 3, 2, 7, 1, 5]);
console.log(arr);
